package leetcode

import kotlinetc.println

//https://leetcode.com/problems/trapping-rain-water/

fun main(args: Array<String>) {

    TrappingRainWater().trap(intArrayOf(1,0,1)).println()
}


/**
 * 当前height[i]是否可以储多少水取决于  height[i]是否小于 其左边的最大高度和右边的最大高度的较小值
 * 如果满足条件，就可以储水
 */
class TrappingRainWater {

    fun trap(height: IntArray): Int {
        var waterArea = 0
        val dp = Array(height.size, { 0 })
        var max = 0
        height.forEachIndexed({ index, heighti ->
            dp[index] = max
            max = Math.max(max, heighti)
        })

        var j = height.size
        //rest max for right perspective
        max = 0
        while (j > 0) {
            j--
            val min = Math.min(dp[j], max)
            max = Math.max(max, height[j])
            if (height[j] < min)
                waterArea += min - height[j]
        }

        return waterArea
    }

}